package sorts;

import javafx.geometry.Side;

import java.util.Arrays;

public class Programma16_16_2 {
    public int[] subSort(int[] array) {
        int start = -1;
        int end = -1;
        int[] res = {start, end};
        if (array == null || array.length < 2) return res;

        int[] arr = new int[array.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = array[i];
        }

        insertSort(array);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(array));

        return res;

    }


    public int[] subSort2(int[] array) {
        if (array == null || array.length == 0) return new int[]{-1, -1};
        int last = -1, first = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] < max) {
                last = i;
            } else {
                max = Math.max(max, array[i]);
            }

            if (array[len - 1 - i] > min) {
                first = len - 1 - i;
            } else {
                min = Math.min(min, array[len - 1 - i]);
            }
        }
        return new int[]{first, last};
    }


    private void insertSort(int[] arr) {
        int start = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            /*for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }*/

            // 插入排序的另一种实现方式
            int insertVal = arr[i];
            int insertIndex = i - 1;

            while (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
                start = Math.max(start, insertIndex + 1);
            }

        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19};
        Programma16_16_2 p = new Programma16_16_2();
        System.out.println(Arrays.toString(p.subSort2(arr)));
    }
}
